package com.demo.study.algorithm.search;

/**
 * 二分查找
 *
 * @author Baymax
 * @since 2024-08-13
 */
public class A02_BinarySearch {

    public static void main(String[] args) {
        int[] array = new int[]{2, 6, 6, 6, 6, 10, 14, 15, 24, 24, 30};
        System.out.println(binarySearchLeftMostInsertPoint(array, 0));
    }

    /**
     * 二分查找-基础版：左闭右闭[i, j]
     */
    public static int binarySearchBase(int[] array, int target) {
        int i = 0, j = array.length - 1;
        while (i <= j) {
            // int m = (i + j) / 2;
            int m = (i + j) >>> 1; // 无符号，二进制右移一位（相当于除以2）
            int mValue = array[m];
            if (target < mValue) {
                j = m - 1;
            } else if (mValue < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 二分查找-修改版：左闭右开[i, j)
     */
    public static int binarySearchRevised(int[] array, int target) {
        int i = 0, j = array.length;
        while (i < j) {
            int m = (i + j) >>> 1;
            int mValue = array[m];
            if (target < mValue) {
                j = m; // 注意
            } else if (mValue < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 二分查找-平衡版
     */
    public static int binarySearchBalance(int[] array, int target) {
        int i = 0, j = array.length;
        while (1 < j - i) { // 注意
            int m = (i + j) >>> 1;
            int mValue = array[m];
            if (target < mValue) {
                j = m; // 注意
            } else {
                i = m; // 注意
            }
        }
        if (array[i] == target) {
            return i;
        }
        return -1;
    }

    /**
     * 二分查找-递归实现
     */
    public static int binarySearchRecursion(int[] array, int target) {
        return doBinarySearchRecursion(array, 0, array.length - 1, target);
    }

    private static int doBinarySearchRecursion(int[] array, int leftIndex, int rightIndex, int target) {
        if (leftIndex > rightIndex) {
            return -1;
        }
        int m = (leftIndex + rightIndex) >>> 1;
        int mValue = array[m];
        if (target < mValue) {
            return doBinarySearchRecursion(array, leftIndex, m - 1, target);
        } else if (mValue < target) {
            return doBinarySearchRecursion(array, m + 1, rightIndex, target);
        } else {
            return m;
        }
    }

    /**
     * 二分查找-最左匹配
     */
    public static int binarySearchLeftMost(int[] array, int target) {
        int i = 0, j = array.length - 1;
        int matched = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            int mValue = array[m];
            if (target < mValue) {
                j = m - 1;
            } else if (mValue < target) {
                i = m + 1;
            } else {
                matched = m;
                j = m - 1;
            }
        }
        return matched;
    }

    /**
     * 二分查找-最右匹配
     */
    public static int binarySearchRightMost(int[] array, int target) {
        int i = 0, j = array.length - 1;
        int matched = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            int mValue = array[m];
            if (target < mValue) {
                j = m - 1;
            } else if (mValue < target) {
                i = m + 1;
            } else {
                matched = m;
                i = m + 1;
            }
        }
        return matched;
    }

    /**
     * 二分查找-Leftmost-插入点
     */
    public static int binarySearchLeftMostInsertPoint(int[] array, int target) {
        int i = 0, j = array.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            int mValue = array[m];
            if (target <= mValue) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }

}
